HW#2 --- last modified March 02 2019 21:25:17..

Solution set.

Due date: Feb 27

Files to be submitted:
  Hw2.tex
  Sorter.zip

Purpose: To learn some more about randomized algorithms, to implement a sorting network (our first parallel algorithm).

Specification:

For the written part of the homework do problems 5.1 (p 118), 27.2-2, 27.3-5, 27.5-3 out of CLRS and submit these in the file Hw2.tex.

For the coding part of the homework, I want you to write a program which can sort input using the sorting network from section 27.5. To do this first write a public class NetworkComparator. This should have one constructor which takes as arguments three integers i, j, n. If i==j or if i>n or j>n this constructor should through an IllegalComparatorArguments exception. Otherwise, it should store these values in fields. NetworkComparator should also have a public method calculate which take as argument a List<int>. It should throw an IllegalSizeException if this list is not of length n. The result of the calculate methods the element at index i in the list after the call is the min of the values in index i and j of the list before the call and the element at index j in the list after the call is the max of the values at i and j from before the call. All other values of the input list should be left unchanged. If the size of the input list is not equal to the n stored in the NetworkComparator, a IllegalSizeException should be thrown.

Next you should build a class NetworkLayer. The constructor for this class should take an integer n for an argument and it should store this value in a field. The constructor should then initialize a field comparatorList of type List<NetworkComparator>. This class should have three public methods one addComparator(NetworkComparator c), unionLayer(NetworkLayer nl), and calculate(List<int> L). addComparator checks to see if c is a NetworkComparator of size n and that there is no element in the comparatorList that involves any of the values i or j that c is comparing. If this is the case c is added to the comparatorList; otherwise, an IllegalComparator exception is thrown. The method calculate throws an IllegalListSize exception if L is not of the same size n as the NetworkLayer; unionLayer checks to see if nl is a NetworkLayer of size n. If this is the case, then unionLayer iterates through the NetworkComparators in nl's list and calls this.addComparator using them; otherwise, an IllegalNetworkLayerException is thrown. The method calculate throws an IllegalListSize exception if L is not of the same size n as the NetworkLayer; otherwise, it iterates through the calculate methods of the comparators in the NetworkLayer calling them on the list L.

After Network Layer, you should make a class Network. The class Network has a constructor which takes an integer argument n which it stores in a field. The constructor then initializes the field layers as an empty List<NetworkLayer> object. This class Network has two public methods addLayer(NetworkLayer nl), and calculate(List<int> L). addLayer checks to see if nl is a NetworkLayer of size n. If this is the case, addLayer adds nl to the list layers; otherwise, an IllegalNetworkLayerException is thrown. Network's method calculate throws an IllegalListSize exception if L is not of the same size n as the Network; otherwise, it iterates through the calculate methods of the NetworkLayer's in the layers list calling them in turn on the list L.

To complete your project, you should have a class BuildSorter with a public static method create(n) which returns a Network of size n based on the sorter of 27.5 out of the book. Then finally, you should have a driver class SortTester which can be run from the command line with a line like:

java SortTester 4 5 6 7 3 9 5 1

This command would then call BuildSorter's create method with the number of things to be sorted in this case 8. It would then call the resulting Network objects calculate method with a list consisting of the things in the command line to be sorted. i.e., 4 5 6 7 3 9 5 1. Finally, the resulting list should be printed to the stardard output. In this case, one should get:

1 3 4 5 5 6 7 9

Your Java project should be submitted in the file Sorter.zip. I will only test your code with lists which are of size a power of 2.

Point Breakdown